Comptage de chemins (graphe orienté) - Exemple

Prenons le graphe ci-dessous.

Sa matrice d'adjacence est  $A=\left(\begin{array}{ccccc}0& 0& 1& 0& 1\\ 1& 0& 0& 0& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0\end{array}\right)$

$M=A^3=\left(\begin{array}{ccccc}1& 1& 0& 1& 0\\ 0& 1& 1& 2& 0\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0\end{array}\right)$

On lit donc (coefficient  $m_{1,2}=1$ ) qu'il y a un chemin de 3 arcs qui va du sommet 1 au sommet 2 ; il s'agit du chemin 1 - 5 - 3 - 2.

En revanche, il n'y a aucun chemin de 2 arcs qui va du sommet 2 au sommet 1 (coefficient  $m_{2,1}=0$ ).

On lit aussi   (coefficient  $m_{2,4}=2$ ) qu'il y a deux chemins de 3 arcs qui vont du sommet 2 au sommet 4.

Il s'agit des chemins :

• 2 - 1 - 5 - 4
• 2 - 1 - 3 - 4

Remarques

• Comme le graphe est orienté, la matrice  $A$  n'est pas symétrique et aucune de ses puissances ne l'est.
• Aucun arc ne part du sommet 4, donc il n'existe aucune possibilité d'aller du sommet 4 à un autre sommet, quel que soit le nombre d'arcs envisagé.